Taxonomies, especially in specific domains, are becoming indispensable to a growing number of applications. For example, in web search, organizing domain-specific queries into a hierarchy provides a way to understand the queries, improve search results, and/or help with query refinement. In online advertising, taxonomies about specific domains (e.g., insurance, online ads) may be used to decide the relatedness between a given query and bidding keywords.